The creation of software and, in particular, the creation of high quality application software has become increasingly expensive. The failure of an application under unforeseen circumstances can create disastrous results and undermine the market acceptance for the application. As a result, increasing efforts are being given to prerelease testing of application software. Based upon the realization that some aspects of software testing can be automated, the prior art has created a number of products specifically directed to aiding the software development engineer in the testing of an application.
In U.S. Pat. No. 4,885,717 to Beck et al., a "diagramming debugger" creates a graphical representation of a sequence of messages that are sent during the operation of an object-oriented program. The debugger displays representations of the transmitting and receiving objects on a screen to enable the development person to understand the internal functioning of the program. As program operations proceed, a box representing an object is added to the display whenever an object first receives a message. Arrows are drawn on the screen between method symbols within display boxes, providing a graphical representation of the order in which messages are sent. In this manner, the debugger "animates" program operation so as to make the sequence of messages sent and methods performed easier to comprehend.
In U.S. Pat. No. 4,730,315 to Saito et al., a diagrammatic method is disclosed for testing a program that enables interactive operations between the user and the program. In this case, a procedure starts with a diagram produced interactively by the user which is then translated into a source program embodying the diagrammatic specifications. Then, the source program is tested and execution results are displayed which indicate the success or lack of success of the test.
In U.S. Pat. No. 4,833,641 to Lerner, a method is described for converting a program's code listing into a hard copy or a display of the program's logic and control flow. This method enables programs that have been altered and re-altered to be analyzed for their logic and control flow.
The International Business Machines Corporation has offered a software application entitled "Software Analysis Test Tool" which enables the software developer to measure and analyze the effectiveness of testing of an application. The Software Analysis Test Tool can both statically and dynamically analyze an application; analyze the coverage of a test performed on the application, and report on the test's coverage. The Software Analysis Test Tool extracts information from the application's compiler listing and displays a diagram of the application's structure. The "tool" enables the user to browse the diagram to understand the software's structure, identify test case design needs and to locate inefficient and/or unused code. In analyzing an application, the Software Analysis Test Tool uses information from the application's execution history files and simulates the application during run time. It highlights paths in a displayed structure diagram that are exercised or not exercised by the test cases. It also is capable of highlighting source code statements to indicate how frequently each statement is exercised during simulation. In this regard, the Software Analysis Test Tool also measures the extent to which the test data has exercised the application structure and then displays the test coverage results in a graphic format. Summary and detailed reports of test coverage results are also generated.
As indicated by the description of the Software Analysis Test Tool, the charting or graphing of a program's structure is known in the prior art. A control flow graph is a known software chart that models the control structure of a program. It is a directed graph comprising nodes and edges. Each node represents a basic block of sequential program code, whereas edges represent possible control paths between blocks, the traversal of a path being dependent upon a conditional statement at the end of a basic block. A basic block is a sequence of program statements that is entered only via the first statement in the sequence, executed sequentially, and is departed only via the last statement.
A directed acyclic graph (DAG) is a control flow graph in which the lines (or arcs or links) that connect nodes have arrows attached that indicate the direction of control flow traversal. Acyclic refers to the lack of cycles (loops) in the graph. Each node has, at most, two branches (edges) that connect to two subsidiary modes. Nodes with two subsidiary nodes have a true or false condition associated with one edge and a complementary condition associated with the other edge.
Normally in a flow graph, there is a unique start node where the graph is entered and a terminal node which is a unique node for exiting the graph. There may be a plurality of terminal nodes depending upon the control flow of the program. All nodes of the flow graph are reachable from the start node. In certain cases, more than one start and terminal node are provided for in the control flow.
Traversal of a sequence of edges in a DAG is called a "walk", and a "path" is defined as a walk through the graph beginning at a start node and ending at a terminal node.
An expert system, a form of which is employed by the invention described herein, is a software application that performs functions in a manner similar to that of a human who is expert in the field. An expert system can solve problems by drawing inferences from a collection of available rules and facts. Expert systems generally have two parts: a knowledge base and an inference engine. The knowledge base is a data base that holds specific facts and rules about the subject under consideration. The inference engine is a part of the expert system that uses the contents of the knowledge base to find an object in the knowledge base that matches a desired format or characteristic.
Inference engines employ various search techniques, e.g., forward-chaining - which is a method of traversing a network of logical AND's and OR's until a terminal point or goal is reached; backward-chaining which is the reverse of forward-chaining where the inference engine begins with a goal and requests information to confirm or deny it, etc. Expert systems/knowledge-bases are available commercially, e.g., The Integrated Reasoning Shell (TIRS) from the International Business Machines Corp; AION, from AION Inc., etc.
Even with the availability of prior art systems for program debugging and testing, the increasing complexity of application software indicates the necessity of providing further automated aids to the software engineer that will enable the identification of error-prone portions of code.
Accordingly, it is an object of this invention to provide a rule-based method for testing programming segments wherein segments that are prone to failure are identified automatically.
It is a further object of this invention to provide an improved method for testing programming segments that enables a series of heuristics to be used to determine the probability of failure of a segment.
It is still another object of this invention to provide a method for program analysis testing that automatically identifies a set of program paths most susceptible to failure.